As electronic commerce grows in popularity, there is an increasing need for systems and methods that protect the rights and interests of the parties involved. One class of problems faced by those conducting transactions remotely via electronic communications networks such as the Internet is that of authenticating messages received from others and providing ways for others to authenticate one's own messages. For example, a party to an electronic transaction will typically want assurance that the other parties are who they purport to be. A party will also want to prevent attackers from misappropriating its identity by, e.g., forging its signature or otherwise assuming its identity in interactions with others. A related problem is that of verifying the integrity of an electronic communication—that is, verifying that the content of the communication has not been modified—when, due to transmission errors, malicious tampering, or a variety of other factors, this may not be the case.
A variety of authentication and validation schemes have been proposed, ranging from the use of passwords to the use of cryptographic signatures. In general, these schemes rely on the existence of a secret shared between the parties to a transaction. By demonstrating knowledge of the shared secret, the parties are able to authenticate themselves to one another. Many cryptographic signature schemes are based on public key cryptography. In public key cryptography, a party creates a signature by applying a strong cryptographic hash algorithm (e.g., SHA-1) to a plaintext message and encrypting the result with the party's private key. The signature message is often as big as the private key modulus, which is typically much larger than the output from the hash algorithm. To verify the signature, a recipient needs to obtain the full message, hash it, decrypt the signature using the signer's public key, and compare the decrypted signature with the hash of the message. If the computed hash is equal to the decrypted signature, then the message is deemed to be authentic.
FIGS. 1A and 1B illustrate the conventional signature generation and detection process described above. Referring to FIG. 1A, a hashing algorithm 102 is applied to a plaintext message 100 to yield a hash or message digest 104. A signature 105 is generated by encrypting message digest 104 using an encryption algorithm 106 and the sender's private key 108. Signature 105 is then transmitted to the recipient along with a copy of message 100. Although, for ease of explanation, FIG. 1A shows message 100 being sent to the recipient in unencrypted form, message 100 could be sent in encrypted form instead, if it were desired to maintain the confidentiality of the message.
Referring to FIG. 1B, the recipient of a message 100′ and a signature 105′ applies hash function 114 to message 100′ to yield message digest 116. The recipient also decrypts signature 105′ using the sender's public key 118 to yield message digest 120. Message digest 116 is then compared with message digest 120. If the two message digests are equal, the recipient can be confident (within the security bounds of the signature scheme) that message 100′ is authentic, as any change an attacker made to message 100′ or signature 105′ would cause the comparison to fail.
A problem with the approach shown in FIGS. 1A and 1B is that the recipient must receive the entire message 100′ before checking its authenticity. The recipient will thus need enough storage to hold the entire message, and must be willing to wait however long is needed to receive it. It is often impractical to meet these limitations. For example, audio, video, and multimedia files are often relatively large, and can thus take a long time to download. In addition, many consumer electronic devices for playing audio, video, or multimedia files have minimal storage and/or processing capacity. As a result, system designers will often wish to allow a consumer to begin using a file before it is completely downloaded, and/or without requiring the consumer's system to store or process the entire file at one time. Thus, for example, multimedia files comprised of multiple MPEG frames are typically designed to be processed on-the-fly by the consumer's device, each MPEG frame being processed while the next frame is received. This is commonly known as “streaming.”
One way to adapt the traditional signature scheme described above for use with streaming applications is to break message 100 into subparts, and to sign each subpart separately. However, this approach has several drawbacks. For example, it can require a relatively large amount of processing power, since both the signature issuer and the signature verifier need to perform numerous relatively-costly public and/or private key operations. In addition, this approach is relatively costly in terms of bandwidth and/or storage requirements, as inserting a large number of cryptographic signatures into the stream can noticeably increase the stream's size. Yet another drawback of this approach is that it fragments the signed message into a set of unrelated, signed sub-messages. This can be less secure and more inconvenient than working with a single, atomic document, as it can be difficult, for example, to determine whether. the sub-messages have been received in the correct order. Thus, there is a need for systems and methods that overcome some or all of these limitations by providing relatively fast, secure, and efficient authentication of data streams and other electronic content.